/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / Intro.tex

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 7b 5c 6d 61 67 74 77 6f | 20 49 6e 74 72 6f 64 75 |{\magtwo| Introdu|
|00000010| 63 74 69 6f 6e 7d 0a 0a | 4f 6e 65 20 6f 66 20 74 |ction}..|One of t|
|00000020| 68 65 20 6d 61 6a 6f 72 | 20 64 69 66 66 65 72 65 |he major| differe|
|00000030| 6e 63 65 73 20 62 65 74 | 77 65 65 6e 20 63 6f 6d |nces bet|ween com|
|00000040| 62 69 6e 61 74 6f 72 69 | 61 6c 20 63 6f 6d 70 75 |binatori|al compu|
|00000050| 74 69 6e 67 0a 61 6e 64 | 20 6f 74 68 65 72 20 61 |ting.and| other a|
|00000060| 72 65 61 73 20 6f 66 20 | 63 6f 6d 70 75 74 69 6e |reas of |computin|
|00000070| 67 20 73 75 63 68 20 61 | 73 20 73 74 61 74 69 73 |g such a|s statis|
|00000080| 74 69 63 73 2c 20 6e 75 | 6d 65 72 69 63 61 6c 0a |tics, nu|merical.|
|00000090| 61 6e 61 6c 79 73 69 73 | 20 61 6e 64 20 6c 69 6e |analysis| and lin|
|000000a0| 65 61 72 20 70 72 6f 67 | 72 61 6d 6d 69 6e 67 20 |ear prog|ramming |
|000000b0| 69 73 20 74 68 65 20 75 | 73 65 20 6f 66 20 63 6f |is the u|se of co|
|000000c0| 6d 70 6c 65 78 20 64 61 | 74 61 20 74 79 70 65 73 |mplex da|ta types|
|000000d0| 2e 20 0a 57 68 69 6c 73 | 74 20 74 68 65 20 62 75 |. .Whils|t the bu|
|000000e0| 69 6c 74 2d 69 6e 20 74 | 79 70 65 73 2c 20 73 75 |ilt-in t|ypes, su|
|000000f0| 63 68 20 61 73 20 69 6e | 74 65 67 65 72 73 2c 20 |ch as in|tegers, |
|00000100| 72 65 61 6c 73 2c 20 76 | 65 63 74 6f 72 73 2c 20 |reals, v|ectors, |
|00000110| 61 6e 64 20 6d 61 74 72 | 69 63 65 73 2c 0a 75 73 |and matr|ices,.us|
|00000120| 75 61 6c 6c 79 20 73 75 | 66 66 69 63 65 20 69 6e |ually su|ffice in|
|00000130| 20 74 68 65 20 6f 74 68 | 65 72 20 61 72 65 61 73 | the oth|er areas|
|00000140| 2c 20 63 6f 6d 62 69 6e | 61 74 6f 72 69 61 6c 20 |, combin|atorial |
|00000150| 63 6f 6d 70 75 74 69 6e | 67 20 72 65 6c 69 65 73 |computin|g relies|
|00000160| 20 68 65 61 76 69 6c 79 | 20 0a 6f 6e 20 74 79 70 | heavily| .on typ|
|00000170| 65 73 20 6c 69 6b 65 20 | 73 74 61 63 6b 73 2c 20 |es like |stacks, |
|00000180| 71 75 65 75 65 73 2c 20 | 64 69 63 74 69 6f 6e 61 |queues, |dictiona|
|00000190| 72 69 65 73 2c 20 73 65 | 71 75 65 6e 63 65 73 2c |ries, se|quences,|
|000001a0| 20 73 6f 72 74 65 64 20 | 73 65 71 75 65 6e 63 65 | sorted |sequence|
|000001b0| 73 2c 20 0a 70 72 69 6f | 72 69 74 79 20 71 75 65 |s, .prio|rity que|
|000001c0| 75 65 73 2c 20 67 72 61 | 70 68 73 2c 20 70 6f 69 |ues, gra|phs, poi|
|000001d0| 6e 74 73 2c 20 73 65 67 | 6d 65 6e 74 73 2c 20 24 |nts, seg|ments, $|
|000001e0| 5c 6c 64 6f 74 73 24 0a | 49 6e 20 74 68 65 20 66 |\ldots$.|In the f|
|000001f0| 61 6c 6c 20 6f 66 20 31 | 39 38 38 2c 20 77 65 20 |all of 1|988, we |
|00000200| 73 74 61 72 74 65 64 20 | 61 20 70 72 6f 6a 65 63 |started |a projec|
|00000210| 74 20 28 63 61 6c 6c 65 | 64 20 7b 5c 62 66 20 4c |t (calle|d {\bf L|
|00000220| 45 44 41 7d 20 66 6f 72 | 20 4c 69 62 72 61 72 79 |EDA} for| Library|
|00000230| 20 6f 66 0a 45 66 66 69 | 63 69 65 6e 74 20 44 61 | of.Effi|cient Da|
|00000240| 74 61 20 74 79 70 65 73 | 20 61 6e 64 20 41 6c 67 |ta types| and Alg|
|00000250| 6f 72 69 74 68 6d 73 29 | 20 74 6f 20 62 75 69 6c |orithms)| to buil|
|00000260| 64 20 61 20 73 6d 61 6c | 6c 2c 20 62 75 74 20 67 |d a smal|l, but g|
|00000270| 72 6f 77 69 6e 67 20 6c | 69 62 72 61 72 79 20 0a |rowing l|ibrary .|
|00000280| 6f 66 20 64 61 74 61 20 | 74 79 70 65 73 20 61 6e |of data |types an|
|00000290| 64 20 61 6c 67 6f 72 69 | 74 68 6d 73 20 69 6e 20 |d algori|thms in |
|000002a0| 61 20 66 6f 72 6d 20 77 | 68 69 63 68 20 61 6c 6c |a form w|hich all|
|000002b0| 6f 77 73 20 74 68 65 6d | 20 74 6f 20 62 65 20 75 |ows them| to be u|
|000002c0| 73 65 64 20 62 79 20 0a | 6e 6f 6e 2d 65 78 70 65 |sed by .|non-expe|
|000002d0| 72 74 73 2e 20 57 65 20 | 68 6f 70 65 20 74 68 61 |rts. We |hope tha|
|000002e0| 74 20 74 68 65 20 73 79 | 73 74 65 6d 20 77 69 6c |t the sy|stem wil|
|000002f0| 6c 20 6e 61 72 72 6f 77 | 20 74 68 65 20 67 61 70 |l narrow| the gap|
|00000300| 20 62 65 74 77 65 65 6e | 20 61 6c 67 6f 72 69 74 | between| algorit|
|00000310| 68 6d 73 0a 72 65 73 65 | 61 72 63 68 2c 20 74 65 |hms.rese|arch, te|
|00000320| 61 63 68 69 6e 67 2c 20 | 61 6e 64 20 69 6d 70 6c |aching, |and impl|
|00000330| 65 6d 65 6e 74 61 74 69 | 6f 6e 2e 20 54 68 65 20 |ementati|on. The |
|00000340| 6d 61 69 6e 20 66 65 61 | 74 75 72 65 73 20 6f 66 |main fea|tures of|
|00000350| 20 4c 45 44 41 20 61 72 | 65 3a 0a 0a 5c 62 65 67 | LEDA ar|e:..\beg|
|00000360| 69 6e 69 74 65 6d 0a 5c | 69 74 65 6d 20 7b 31 2e |initem.\|item {1.|
|00000370| 7d 0a 20 20 20 20 4c 45 | 44 41 20 70 72 6f 76 69 |}.    LE|DA provi|
|00000380| 64 65 73 20 61 20 73 69 | 7a 61 62 6c 65 20 63 6f |des a si|zable co|
|00000390| 6c 6c 65 63 74 69 6f 6e | 20 6f 66 20 64 61 74 61 |llection| of data|
|000003a0| 20 74 79 70 65 73 20 61 | 6e 64 20 61 6c 67 6f 72 | types a|nd algor|
|000003b0| 69 74 68 6d 73 20 69 6e | 20 61 20 66 6f 72 6d 20 |ithms in| a form |
|000003c0| 0a 20 20 20 20 77 68 69 | 63 68 20 61 6c 6c 6f 77 |.    whi|ch allow|
|000003d0| 73 20 74 68 65 6d 20 74 | 6f 20 62 65 20 75 73 65 |s them t|o be use|
|000003e0| 64 20 62 79 20 6e 6f 6e | 2d 65 78 70 65 72 74 73 |d by non|-experts|
|000003f0| 2e 20 49 6e 20 74 68 65 | 20 63 75 72 72 65 6e 74 |. In the| current|
|00000400| 20 76 65 72 73 69 6f 6e | 2c 20 74 68 69 73 0a 20 | version|, this. |
|00000410| 20 20 20 63 6f 6c 6c 65 | 63 74 69 6f 6e 20 69 6e |   colle|ction in|
|00000420| 63 6c 75 64 65 73 20 6d | 6f 73 74 20 6f 66 20 74 |cludes m|ost of t|
|00000430| 68 65 20 64 61 74 61 20 | 74 79 70 65 73 20 61 6e |he data |types an|
|00000440| 64 20 61 6c 67 6f 72 69 | 74 68 6d 73 20 64 65 73 |d algori|thms des|
|00000450| 63 72 69 62 65 64 20 69 | 6e 20 74 68 65 20 0a 20 |cribed i|n the . |
|00000460| 20 20 20 74 65 78 74 20 | 62 6f 6f 6b 73 20 6f 66 |   text |books of|
|00000470| 20 74 68 65 20 61 72 65 | 61 2e 20 0a 0a 5c 69 74 | the are|a. ..\it|
|00000480| 65 6d 20 7b 32 2e 7d 0a | 20 20 20 20 4c 45 44 41 |em {2.}.|    LEDA|
|00000490| 20 67 69 76 65 73 20 61 | 20 70 72 65 63 69 73 65 | gives a| precise|
|000004a0| 20 61 6e 64 20 72 65 61 | 64 61 62 6c 65 20 73 70 | and rea|dable sp|
|000004b0| 65 63 69 66 69 63 61 74 | 69 6f 6e 20 66 6f 72 20 |ecificat|ion for |
|000004c0| 65 61 63 68 20 6f 66 20 | 74 68 65 20 64 61 74 61 |each of |the data|
|000004d0| 20 74 79 70 65 73 20 0a | 20 20 20 20 61 6e 64 20 | types .|    and |
|000004e0| 61 6c 67 6f 72 69 74 68 | 6d 73 20 6d 65 6e 74 69 |algorith|ms menti|
|000004f0| 6f 6e 65 64 20 61 62 6f | 76 65 2e 20 20 54 68 65 |oned abo|ve.  The|
|00000500| 20 73 70 65 63 69 66 69 | 63 61 74 69 6f 6e 73 20 | specifi|cations |
|00000510| 61 72 65 20 73 68 6f 72 | 74 20 28 74 79 70 69 63 |are shor|t (typic|
|00000520| 61 6c 6c 79 2c 20 0a 20 | 20 20 20 6e 6f 74 20 6d |ally, . |   not m|
|00000530| 6f 72 65 20 74 68 61 6e | 20 61 20 70 61 67 65 29 |ore than| a page)|
|00000540| 2c 20 67 65 6e 65 72 61 | 6c 20 28 73 6f 20 61 73 |, genera|l (so as|
|00000550| 20 74 6f 20 61 6c 6c 6f | 77 20 73 65 76 65 72 61 | to allo|w severa|
|00000560| 6c 20 69 6d 70 6c 65 6d | 65 6e 74 61 74 69 6f 6e |l implem|entation|
|00000570| 73 29 2c 20 0a 20 20 20 | 20 61 6e 64 20 61 62 73 |s), .   | and abs|
|00000580| 74 72 61 63 74 20 28 73 | 6f 20 61 73 20 74 6f 20 |tract (s|o as to |
|00000590| 68 69 64 65 20 61 6c 6c | 20 64 65 74 61 69 6c 73 |hide all| details|
|000005a0| 20 6f 66 20 74 68 65 20 | 69 6d 70 6c 65 6d 65 6e | of the |implemen|
|000005b0| 74 61 74 69 6f 6e 29 2e | 20 0a 0a 5c 69 74 65 6d |tation).| ..\item|
|000005c0| 20 7b 33 2e 7d 0a 20 20 | 20 20 46 6f 72 20 6d 61 | {3.}.  |  For ma|
|000005d0| 6e 79 20 65 66 66 69 63 | 69 65 6e 74 20 64 61 74 |ny effic|ient dat|
|000005e0| 61 20 73 74 72 75 63 74 | 75 72 65 73 20 61 63 63 |a struct|ures acc|
|000005f0| 65 73 73 20 62 79 20 70 | 6f 73 69 74 69 6f 6e 20 |ess by p|osition |
|00000600| 69 73 20 69 6d 70 6f 72 | 74 61 6e 74 2e 20 49 6e |is impor|tant. In|
|00000610| 20 0a 20 20 20 20 4c 45 | 44 41 2c 20 77 65 20 75 | .    LE|DA, we u|
|00000620| 73 65 20 61 6e 20 69 74 | 65 6d 20 63 6f 6e 63 65 |se an it|em conce|
|00000630| 70 74 20 74 6f 20 63 61 | 73 74 20 70 6f 73 69 74 |pt to ca|st posit|
|00000640| 69 6f 6e 73 20 69 6e 74 | 6f 20 61 6e 20 61 62 73 |ions int|o an abs|
|00000650| 74 72 61 63 74 20 66 6f | 72 6d 2e 20 57 65 20 0a |tract fo|rm. We .|
|00000660| 20 20 20 20 6d 65 6e 74 | 69 6f 6e 20 74 68 61 74 |    ment|ion that|
|00000670| 20 6d 6f 73 74 20 6f 66 | 20 74 68 65 20 73 70 65 | most of| the spe|
|00000680| 63 69 66 69 63 61 74 69 | 6f 6e 73 20 67 69 76 65 |cificati|ons give|
|00000690| 6e 20 69 6e 20 74 68 65 | 20 4c 45 44 41 20 6d 61 |n in the| LEDA ma|
|000006a0| 6e 75 61 6c 20 75 73 65 | 20 74 68 69 73 20 0a 20 |nual use| this . |
|000006b0| 20 20 20 63 6f 6e 63 65 | 70 74 2c 20 69 2e 65 2e |   conce|pt, i.e.|
|000006c0| 2c 20 74 68 65 20 63 6f | 6e 63 65 70 74 20 69 73 |, the co|ncept is|
|000006d0| 20 61 64 65 71 75 61 74 | 65 20 66 6f 72 20 74 68 | adequat|e for th|
|000006e0| 65 20 64 65 73 63 72 69 | 70 74 69 6f 6e 20 6f 66 |e descri|ption of|
|000006f0| 20 6d 61 6e 79 20 64 61 | 74 61 20 0a 20 20 20 20 | many da|ta .    |
|00000700| 74 79 70 65 73 2e 20 0a | 0a 5c 69 74 65 6d 20 7b |types. .|.\item {|
|00000710| 34 2e 7d 0a 20 20 20 20 | 4c 45 44 41 20 63 6f 6e |4.}.    |LEDA con|
|00000720| 74 61 69 6e 73 20 65 66 | 66 69 63 69 65 6e 74 20 |tains ef|ficient |
|00000730| 69 6d 70 6c 65 6d 65 6e | 74 61 74 69 6f 6e 73 20 |implemen|tations |
|00000740| 66 6f 72 20 65 61 63 68 | 20 6f 66 20 74 68 65 20 |for each| of the |
|00000750| 64 61 74 61 20 74 79 70 | 65 73 2c 20 65 2e 67 2e |data typ|es, e.g.|
|00000760| 2c 20 0a 20 20 20 20 46 | 69 62 6f 6e 61 63 63 69 |, .    F|ibonacci|
|00000770| 20 68 65 61 70 73 20 66 | 6f 72 20 70 72 69 6f 72 | heaps f|or prior|
|00000780| 69 74 79 20 71 75 65 75 | 65 73 2c 20 73 6b 69 70 |ity queu|es, skip|
|00000790| 20 6c 69 73 74 73 20 61 | 6e 64 20 64 79 6e 61 6d | lists a|nd dynam|
|000007a0| 69 63 20 70 65 72 66 65 | 63 74 20 0a 20 20 20 20 |ic perfe|ct .    |
|000007b0| 68 61 73 68 69 6e 67 20 | 66 6f 72 20 64 69 63 74 |hashing |for dict|
|000007c0| 69 6f 6e 61 72 69 65 73 | 2c 20 2e 2e 2e 0a 0a 0a |ionaries|, ......|
|000007d0| 5c 69 74 65 6d 20 7b 35 | 2e 7d 0a 20 20 20 20 4c |\item {5|.}.    L|
|000007e0| 45 44 41 20 63 6f 6e 74 | 61 69 6e 73 20 61 20 63 |EDA cont|ains a c|
|000007f0| 6f 6d 66 6f 72 74 61 62 | 6c 65 20 64 61 74 61 20 |omfortab|le data |
|00000800| 74 79 70 65 20 67 72 61 | 70 68 2e 20 49 74 20 6f |type gra|ph. It o|
|00000810| 66 66 65 72 73 20 74 68 | 65 20 73 74 61 6e 64 61 |ffers th|e standa|
|00000820| 72 64 20 0a 20 20 20 20 | 69 74 65 72 61 74 69 6f |rd .    |iteratio|
|00000830| 6e 73 20 73 75 63 68 20 | 61 73 20 60 60 66 6f 72 |ns such |as ``for|
|00000840| 20 61 6c 6c 20 6e 6f 64 | 65 73 20 76 20 6f 66 20 | all nod|es v of |
|00000850| 61 20 67 72 61 70 68 20 | 47 20 64 6f 27 27 20 6f |a graph |G do'' o|
|00000860| 72 20 60 60 66 6f 72 20 | 61 6c 6c 20 0a 20 20 20 |r ``for |all .   |
|00000870| 20 6e 65 69 67 68 62 6f | 72 73 20 77 20 6f 66 20 | neighbo|rs w of |
|00000880| 76 20 64 6f 27 27 2c 20 | 69 74 20 61 6c 6c 6f 77 |v do'', |it allow|
|00000890| 73 20 74 6f 20 61 64 64 | 20 61 6e 64 20 64 65 6c |s to add| and del|
|000008a0| 65 74 65 20 76 65 72 74 | 69 63 65 73 20 61 6e 64 |ete vert|ices and|
|000008b0| 20 65 64 67 65 73 20 0a | 20 20 20 20 61 6e 64 20 | edges .|    and |
|000008c0| 69 74 20 6f 66 66 65 72 | 73 20 61 72 72 61 79 73 |it offer|s arrays|
|000008d0| 20 61 6e 64 20 6d 61 74 | 72 69 63 65 73 20 69 6e | and mat|rices in|
|000008e0| 64 65 78 65 64 20 62 79 | 20 6e 6f 64 65 73 20 61 |dexed by| nodes a|
|000008f0| 6e 64 20 65 64 67 65 73 | 2c 2e 2e 2e 20 20 0a 20 |nd edges|,...  . |
|00000900| 20 20 20 54 68 65 20 64 | 61 74 61 20 74 79 70 65 |   The d|ata type|
|00000910| 20 67 72 61 70 68 20 61 | 6c 6c 6f 77 73 20 74 6f | graph a|llows to|
|00000920| 20 77 72 69 74 65 20 70 | 72 6f 67 72 61 6d 73 20 | write p|rograms |
|00000930| 66 6f 72 20 67 72 61 70 | 68 20 70 72 6f 62 6c 65 |for grap|h proble|
|00000940| 6d 73 20 69 6e 20 61 20 | 0a 20 20 20 20 66 6f 72 |ms in a |.    for|
|00000950| 6d 20 63 6c 6f 73 65 20 | 74 6f 20 74 68 65 20 74 |m close |to the t|
|00000960| 79 70 69 63 61 6c 20 74 | 65 78 74 20 62 6f 6f 6b |ypical t|ext book|
|00000970| 20 70 72 65 73 65 6e 74 | 61 74 69 6f 6e 2e 0a 0a | present|ation...|
|00000980| 0a 5c 69 74 65 6d 20 7b | 36 2e 7d 0a 20 20 20 20 |.\item {|6.}.    |
|00000990| 4c 45 44 41 20 69 73 20 | 69 6d 70 6c 65 6d 65 6e |LEDA is |implemen|
|000009a0| 74 65 64 20 62 79 20 61 | 20 5c 43 43 20 63 6c 61 |ted by a| \CC cla|
|000009b0| 73 73 20 6c 69 62 72 61 | 72 79 2e 20 49 74 20 63 |ss libra|ry. It c|
|000009c0| 61 6e 20 62 65 20 75 73 | 65 64 20 77 69 74 68 20 |an be us|ed with |
|000009d0| 61 6c 6c 6d 6f 73 74 0a | 20 20 20 20 61 6e 79 20 |allmost.|    any |
|000009e0| 5c 43 43 20 63 6f 6d 70 | 69 6c 65 72 20 28 65 2e |\CC comp|iler (e.|
|000009f0| 67 2e 2c 20 63 66 72 6f | 6e 74 32 2c 20 63 66 72 |g., cfro|nt2, cfr|
|00000a00| 6f 6e 74 33 2c 20 67 2b | 2b 2d 31 2c 20 67 2b 2b |ont3, g+|+-1, g++|
|00000a10| 2d 32 2c 20 62 63 63 2c | 20 7a 74 63 29 2e 0a 0a |-2, bcc,| ztc)...|
|00000a20| 0a 5c 76 66 69 6c 6c 5c | 65 6a 65 63 74 0a 5c 69 |.\vfill\|eject.\i|
|00000a30| 74 65 6d 20 7b 37 2e 7d | 0a 20 20 20 20 7b 4c 45 |tem {7.}|.    {LE|
|00000a40| 44 41 20 69 73 20 61 76 | 61 69 6c 61 62 6c 65 20 |DA is av|ailable |
|00000a50| 62 79 20 61 6e 6f 6e 79 | 6d 6f 75 73 20 66 74 70 |by anony|mous ftp|
|00000a60| 20 66 72 6f 6d 20 5c 6e | 6c 0a 20 20 20 20 20 7b | from \n|l.     {|
|00000a70| 5c 62 66 20 66 74 70 2e | 63 73 2e 75 6e 69 2d 73 |\bf ftp.|cs.uni-s|
|00000a80| 62 2e 64 65 7d 20 20 20 | 20 20 20 20 20 28 31 33 |b.de}   |     (13|
|00000a90| 34 2e 39 36 2e 37 2e 32 | 35 34 29 20 2f 70 75 62 |4.96.7.2|54) /pub|
|00000aa0| 2f 4c 45 44 41 5c 6e 6c | 0a 25 20 20 20 20 7b 5c |/LEDA\nl|.%    {\|
|00000ab0| 62 66 20 66 74 70 2e 6d | 61 74 68 73 2e 77 61 72 |bf ftp.m|aths.war|
|00000ac0| 77 69 63 6b 2e 61 63 2e | 75 6b 7d 20 28 31 33 37 |wick.ac.|uk} (137|
|00000ad0| 2e 32 30 35 2e 32 33 32 | 2e 34 29 20 2f 70 75 62 |.205.232|.4) /pub|
|00000ae0| 2f 73 6f 75 72 63 65 73 | 2f 63 2b 2b 5c 6e 6c 0a |/sources|/c++\nl.|
|00000af0| 20 20 20 20 54 68 65 20 | 44 69 73 74 72 69 62 75 |    The |Distribu|
|00000b00| 74 69 6f 6e 20 63 6f 6e | 74 61 69 6e 73 20 61 6c |tion con|tains al|
|00000b10| 6c 20 73 6f 75 72 63 65 | 73 2c 20 69 6e 73 74 61 |l source|s, insta|
|00000b20| 6c 6c 61 74 69 6f 6e 20 | 69 6e 73 74 72 75 63 74 |llation |instruct|
|00000b30| 69 6f 6e 73 2c 20 61 20 | 0a 20 20 20 20 74 65 63 |ions, a |.    tec|
|00000b40| 68 6e 69 63 61 6c 20 72 | 65 70 6f 72 74 2c 20 61 |hnical r|eport, a|
|00000b50| 6e 64 20 74 68 65 20 4c | 45 44 41 20 75 73 65 72 |nd the L|EDA user|
|00000b60| 20 6d 61 6e 75 61 6c 2e | 7d 0a 0a 0a 5c 69 74 65 | manual.|}...\ite|
|00000b70| 6d 20 7b 38 2e 7d 0a 20 | 20 20 20 4c 45 44 41 20 |m {8.}. |   LEDA |
|00000b80| 69 73 20 6e 6f 74 20 69 | 6e 20 74 68 65 20 70 75 |is not i|n the pu|
|00000b90| 62 6c 69 63 20 64 6f 6d | 61 69 6e 2c 20 62 75 74 |blic dom|ain, but|
|00000ba0| 20 63 61 6e 20 62 65 20 | 75 73 65 64 20 66 72 65 | can be |used fre|
|00000bb0| 65 6c 79 20 66 6f 72 20 | 72 65 73 65 61 72 63 68 |ely for |research|
|00000bc0| 20 0a 20 20 20 20 61 6e | 64 20 74 65 61 63 68 69 | .    an|d teachi|
|00000bd0| 6e 67 2e 20 41 20 63 6f | 6d 6d 65 72 63 69 61 6c |ng. A co|mmercial|
|00000be0| 20 6c 69 63 65 6e 73 65 | 20 69 73 20 61 76 61 69 | license| is avai|
|00000bf0| 6c 61 62 6c 65 20 66 72 | 6f 6d 20 74 68 65 20 61 |lable fr|om the a|
|00000c00| 75 74 6f 72 2e 0a 0a 5c | 65 6e 64 69 74 65 6d 0a |utor...\|enditem.|
|00000c10| 0a 54 68 69 73 20 6d 61 | 6e 75 61 6c 20 63 6f 6e |.This ma|nual con|
|00000c20| 74 61 69 6e 73 20 74 68 | 65 20 73 70 65 63 69 66 |tains th|e specif|
|00000c30| 69 63 61 74 69 6f 6e 73 | 20 6f 66 20 61 6c 6c 20 |ications| of all |
|00000c40| 64 61 74 61 20 74 79 70 | 65 73 20 61 6e 64 20 61 |data typ|es and a|
|00000c50| 6c 67 6f 72 69 74 68 6d | 73 20 0a 63 75 72 72 65 |lgorithm|s .curre|
|00000c60| 6e 74 6c 79 20 61 76 61 | 69 6c 61 62 6c 65 20 69 |ntly ava|ilable i|
|00000c70| 6e 20 4c 45 44 41 2e 20 | 55 73 65 72 73 20 73 68 |n LEDA. |Users sh|
|00000c80| 6f 75 6c 64 20 62 65 20 | 66 61 6d 69 6c 69 61 72 |ould be |familiar|
|00000c90| 20 77 69 74 68 20 74 68 | 65 20 5c 43 43 20 0a 70 | with th|e \CC .p|
|00000ca0| 72 6f 67 72 61 6d 6d 69 | 6e 67 20 6c 61 6e 67 75 |rogrammi|ng langu|
|00000cb0| 61 67 65 20 28 73 65 65 | 20 5b 53 39 31 5d 20 6f |age (see| [S91] o|
|00000cc0| 72 20 5b 4c 38 39 5d 29 | 2e 20 54 68 65 20 6d 61 |r [L89])|. The ma|
|00000cd0| 69 6e 20 63 6f 6e 63 65 | 70 74 73 20 61 6e 64 20 |in conce|pts and |
|00000ce0| 73 6f 6d 65 20 0a 69 6d | 70 6c 65 6d 65 6e 74 61 |some .im|plementa|
|00000cf0| 74 69 6f 6e 20 64 65 74 | 61 69 6c 73 20 6f 66 20 |tion det|ails of |
|00000d00| 4c 45 44 41 20 61 72 65 | 20 64 65 73 63 72 69 62 |LEDA are| describ|
|00000d10| 65 64 20 69 6e 20 5b 4d | 4e 38 39 5d 20 61 6e 64 |ed in [M|N89] and|
|00000d20| 20 5b 4e 39 32 5d 2e 20 | 54 68 65 20 6d 61 6e 75 | [N92]. |The manu|
|00000d30| 61 6c 20 0a 69 73 20 73 | 74 72 75 63 74 75 72 65 |al .is s|tructure|
|00000d40| 64 20 61 73 20 66 6f 6c | 6c 6f 77 73 3a 20 49 6e |d as fol|lows: In|
|00000d50| 20 63 68 61 70 74 65 72 | 20 6f 6e 65 2c 20 77 68 | chapter| one, wh|
|00000d60| 69 63 68 20 69 73 20 61 | 20 70 72 65 72 65 71 75 |ich is a| prerequ|
|00000d70| 69 73 69 74 65 20 66 6f | 72 20 61 6c 6c 0a 6f 74 |isite fo|r all.ot|
|00000d80| 68 65 72 20 63 68 61 70 | 74 65 72 73 2c 20 77 65 |her chap|ters, we|
|00000d90| 20 64 69 73 63 75 73 73 | 20 74 68 65 20 62 61 73 | discuss| the bas|
|00000da0| 69 63 20 63 6f 6e 63 65 | 70 74 73 20 61 6e 64 20 |ic conce|pts and |
|00000db0| 6e 6f 74 61 74 69 6f 6e | 73 20 75 73 65 64 20 69 |notation|s used i|
|00000dc0| 6e 20 4c 45 44 41 2e 0a | 54 68 65 20 6f 74 68 65 |n LEDA..|The othe|
|00000dd0| 72 20 63 68 61 70 74 65 | 72 73 20 64 65 66 69 6e |r chapte|rs defin|
|00000de0| 65 20 74 68 65 20 64 61 | 74 61 20 74 79 70 65 73 |e the da|ta types|
|00000df0| 20 61 6e 64 20 61 6c 67 | 6f 72 69 74 68 6d 73 20 | and alg|orithms |
|00000e00| 61 76 61 69 6c 61 62 6c | 65 20 69 6e 0a 4c 45 44 |availabl|e in.LED|
|00000e10| 41 20 61 6e 64 20 67 69 | 76 65 20 65 78 61 6d 70 |A and gi|ve examp|
|00000e20| 6c 65 73 20 6f 66 20 74 | 68 65 69 72 20 75 73 65 |les of t|heir use|
|00000e30| 2e 20 54 68 65 73 65 20 | 63 68 61 70 74 65 72 73 |. These |chapters|
|00000e40| 20 63 61 6e 20 62 65 20 | 63 6f 6e 73 75 6c 74 65 | can be |consulte|
|00000e50| 64 0a 69 6e 64 65 70 65 | 6e 64 65 6e 74 6c 79 20 |d.indepe|ndently |
|00000e60| 66 72 6f 6d 20 6f 6e 65 | 20 61 6e 6f 74 68 65 72 |from one| another|
|00000e70| 2e 0a 0a 5c 62 69 67 73 | 6b 69 70 0a 5c 62 69 67 |...\bigs|kip.\big|
|00000e80| 73 6b 69 70 0a 7b 5c 6d | 61 67 6f 6e 65 62 66 20 |skip.{\m|agonebf |
|00000e90| 56 65 72 73 69 6f 6e 20 | 33 2e 30 7d 0a 0a 54 68 |Version |3.0}..Th|
|00000ea0| 65 20 6d 6f 73 74 20 69 | 6d 70 6f 72 74 61 6e 74 |e most i|mportant|
|00000eb0| 20 63 68 61 6e 67 65 73 | 20 77 69 74 68 20 72 65 | changes| with re|
|00000ec0| 73 70 65 63 74 20 74 6f | 20 70 72 65 76 69 6f 75 |spect to| previou|
|00000ed0| 73 20 76 65 72 73 69 6f | 6e 73 20 61 72 65 0a 5c |s versio|ns are.\|
|00000ee0| 62 65 67 69 6e 69 74 65 | 6d 0a 5c 69 74 65 6d 20 |beginite|m.\item |
|00000ef0| 7b 61 29 7d 0a 50 61 72 | 61 6d 65 74 65 72 69 7a |{a)}.Par|ameteriz|
|00000f00| 65 64 20 64 61 74 61 20 | 74 79 70 65 73 20 61 72 |ed data |types ar|
|00000f10| 65 20 72 65 61 6c 69 7a | 65 64 20 62 79 20 5c 43 |e realiz|ed by \C|
|00000f20| 43 20 74 65 6d 70 6c 61 | 74 65 73 2e 20 49 6e 20 |C templa|tes. In |
|00000f30| 70 61 72 74 69 63 75 6c | 61 72 2c 20 0a 7b 5c 69 |particul|ar, .{\i|
|00000f40| 74 20 64 65 63 6c 61 72 | 65 7d 20 6d 61 63 72 6f |t declar|e} macro|
|00000f50| 73 20 75 73 65 64 20 69 | 6e 20 70 72 65 76 69 6f |s used i|n previo|
|00000f60| 75 73 20 76 65 72 73 69 | 6f 6e 73 20 61 72 65 20 |us versi|ons are |
|00000f70| 6e 6f 77 20 6f 62 73 6f | 6c 65 74 65 20 61 6e 64 |now obso|lete and|
|00000f80| 20 74 68 65 20 0a 73 79 | 6e 74 61 78 20 66 6f 72 | the .sy|ntax for|
|00000f90| 20 61 20 70 61 72 61 6d | 65 74 65 72 69 7a 65 64 | a param|eterized|
|00000fa0| 20 64 61 74 61 20 74 79 | 70 65 20 24 44 24 20 77 | data ty|pe $D$ w|
|00000fb0| 69 74 68 20 74 79 70 65 | 20 70 61 72 61 6d 65 74 |ith type| paramet|
|00000fc0| 65 72 73 20 24 54 5f 31 | 2c 5c 64 6f 74 73 2c 54 |ers $T_1|,\dots,T|
|00000fd0| 5f 6b 24 20 0a 69 73 20 | 24 44 5c 3c 54 5f 31 2c |_k$ .is |$D\<T_1,|
|00000fe0| 5c 64 6f 74 73 2c 54 5f | 6b 5c 3e 24 20 28 63 66 |\dots,T_|k\>$ (cf|
|00000ff0| 2e 7e 73 65 63 74 69 6f | 6e 7e 31 2e 32 29 2e 20 |.~sectio|n~1.2). |
|00001000| 46 6f 72 20 5c 43 43 20 | 63 6f 6d 70 69 6c 65 72 |For \CC |compiler|
|00001010| 73 20 6e 6f 74 20 0a 73 | 75 70 70 6f 72 74 69 6e |s not .s|upportin|
|00001020| 67 20 74 65 6d 70 6c 61 | 74 65 73 20 74 68 65 72 |g templa|tes ther|
|00001030| 65 20 69 73 20 73 74 69 | 6c 6c 20 61 20 6e 6f 6e |e is sti|ll a non|
|00001040| 2d 74 65 6d 70 6c 61 74 | 65 20 76 61 72 69 61 6e |-templat|e varian|
|00001050| 74 20 28 4c 45 44 41 2d | 4e 2d 33 2e 30 29 20 0a |t (LEDA-|N-3.0) .|
|00001060| 61 76 61 69 6c 61 62 6c | 65 2e 0a 0a 5c 69 74 65 |availabl|e...\ite|
|00001070| 6d 20 7b 62 29 7d 0a 41 | 72 62 69 74 72 61 72 79 |m {b)}.A|rbitrary|
|00001080| 20 64 61 74 61 20 74 79 | 70 65 73 20 28 6e 6f 74 | data ty|pes (not|
|00001090| 20 6f 6e 6c 79 20 70 6f | 69 6e 74 65 72 20 61 6e | only po|inter an|
|000010a0| 64 20 73 69 6d 70 6c 65 | 20 74 79 70 65 73 29 20 |d simple| types) |
|000010b0| 63 61 6e 20 62 65 20 75 | 73 65 64 20 61 73 0a 61 |can be u|sed as.a|
|000010c0| 63 74 75 61 6c 20 74 79 | 70 65 20 70 61 72 61 6d |ctual ty|pe param|
|000010d0| 65 74 65 72 73 20 28 63 | 66 2e 7e 73 65 63 74 69 |eters (c|f.~secti|
|000010e0| 6f 6e 7e 31 2e 32 29 2e | 20 0a 0a 5c 69 74 65 6d |on~1.2).| ..\item|
|000010f0| 20 7b 63 29 7d 0a 46 6f | 72 20 6d 61 6e 79 20 6f | {c)}.Fo|r many o|
|00001100| 66 20 74 68 65 20 70 61 | 72 61 6d 65 74 65 72 69 |f the pa|rameteri|
|00001110| 7a 65 64 20 64 61 74 61 | 20 74 79 70 65 73 20 28 |zed data| types (|
|00001120| 69 6e 20 74 68 65 20 63 | 75 72 72 65 6e 74 20 76 |in the c|urrent v|
|00001130| 65 72 73 69 6f 6e 3a 20 | 64 69 63 74 69 6f 6e 61 |ersion: |dictiona|
|00001140| 72 79 2c 20 0a 70 72 69 | 6f 72 69 74 79 20 71 75 |ry, .pri|ority qu|
|00001150| 65 75 65 2c 20 64 5c 5f | 61 72 72 61 79 2c 20 61 |eue, d\_|array, a|
|00001160| 6e 64 20 73 6f 72 74 73 | 65 71 29 20 74 68 65 72 |nd sorts|eq) ther|
|00001170| 65 20 65 78 69 73 74 20 | 76 61 72 69 61 6e 74 73 |e exist |variants|
|00001180| 20 74 61 6b 69 6e 67 20 | 61 6e 20 61 64 64 69 74 | taking |an addit|
|00001190| 69 6f 6e 61 6c 0a 64 61 | 74 61 20 73 74 72 75 63 |ional.da|ta struc|
|000011a0| 74 75 72 65 20 70 61 72 | 61 6d 65 74 65 72 20 66 |ture par|ameter f|
|000011b0| 6f 72 20 63 68 6f 6f 73 | 69 6e 67 20 61 20 70 61 |or choos|ing a pa|
|000011c0| 72 74 69 63 75 6c 61 72 | 20 69 6d 70 6c 65 6d 65 |rticular| impleme|
|000011d0| 6e 74 61 74 69 6f 6e 20 | 0a 28 63 66 2e 7e 73 65 |ntation |.(cf.~se|
|000011e0| 63 74 69 6f 6e 7e 31 2e | 33 29 2e 0a 0a 5c 69 74 |ction~1.|3)...\it|
|000011f0| 65 6d 20 7b 64 29 7d 0a | 54 68 65 20 4c 45 44 41 |em {d)}.|The LEDA|
|00001200| 20 6d 65 6d 6f 72 79 20 | 6d 61 6e 61 67 65 6d 65 | memory |manageme|
|00001210| 6e 74 20 73 79 73 74 65 | 6d 20 63 61 6e 20 62 65 |nt syste|m can be|
|00001220| 20 63 75 73 74 6f 6d 69 | 7a 65 64 20 66 6f 72 20 | customi|zed for |
|00001230| 75 73 65 72 2d 64 65 66 | 69 6e 65 64 20 63 6c 61 |user-def|ined cla|
|00001240| 73 73 65 73 0a 28 63 66 | 2e 7e 73 65 63 74 69 6f |sses.(cf|.~sectio|
|00001250| 6e 7e 37 2e 33 29 0a 0a | 5c 69 74 65 6d 7b 65 29 |n~7.3)..|\item{e)|
|00001260| 7d 0a 54 68 65 20 65 66 | 66 69 63 69 65 6e 63 79 |}.The ef|ficiency|
|00001270| 20 6f 66 20 6d 61 6e 79 | 20 64 61 74 61 20 74 79 | of many| data ty|
|00001280| 70 65 73 20 61 6e 64 20 | 61 6c 67 6f 72 69 74 68 |pes and |algorith|
|00001290| 6d 73 20 68 61 73 20 62 | 65 65 6e 20 69 6d 70 72 |ms has b|een impr|
|000012a0| 6f 76 65 64 2e 0a 5c 65 | 6e 64 69 74 65 6d 0a 0a |oved..\e|nditem..|
|000012b0| 53 65 65 20 61 6c 73 6f | 20 74 68 65 20 60 60 43 |See also| the ``C|
|000012c0| 68 61 6e 67 65 73 22 20 | 66 69 6c 65 20 69 6e 20 |hanges" |file in |
|000012d0| 74 68 65 20 4c 45 44 41 | 20 72 6f 6f 74 20 64 69 |the LEDA| root di|
|000012e0| 72 65 63 74 6f 72 79 2e | 0a 0a 0a 5c 76 66 69 6c |rectory.|...\vfil|
|000012f0| 6c 5c 65 6a 65 63 74 0a | 0a                      |l\eject.|.       |
+--------+-------------------------+-------------------------+--------+--------+